import com.oracle.xmlns.internal.webservices.jaxws_databinding.XmlOneway;

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution1 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = count[i] = 1;
        }

        int retlen = 1, retcount = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }
            if (retlen == len[i]) {
                retcount += count[i];
            } else if (retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }

        return retcount;
    }
}


class Solution2 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = count[i] = 1;
        }

        int retlen = 1, retcount = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    } else if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }
                }
            }

            if (retlen == len[i]) {
                retcount += count[i];
            } else if (retlen < len[i]) {
                retlen = len[i];
                retcount = count[i];
            }
        }

        return retcount;
    }
}

class Solution3 {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int[] hash = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            char ch1 = s1.charAt(i), ch2 = s2.charAt(i);
            hash[ch1 - 'a']++;
            hash[ch2 - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution4 {
    public int lastStoneWeight(int[] stones) {
        int n = stones.length;
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
            return b - a;
        });
        for (int x : stones) {
            queue.add(x);
        }
        while (queue.size() > 1) {
            int x = queue.poll();
            int y = queue.poll();
            System.out.println(x + " " + y);
            if (x != y) {
                queue.add(x - y);
            }
        }
        if (queue.isEmpty()) return 0;
        return queue.poll();
    }
}

class Solution5 {
    public int countCharacters(String[] words, String chars) {
        int[] hash = new int[26];
        for (char ch : chars.toCharArray()) {
            hash[ch - 'a']++;
        }
        int count = 0;
        for (String str : words) {
            if (check(str, hash)) {
                count += str.length();
                System.out.println(str);
            }
        }
        return count;
    }

    public boolean check(String str, int[] hash) {
        int[] tmp = Arrays.copyOf(hash, 26);
        for (char ch : str.toCharArray()) {
            if (tmp[ch - 'a'] == 0) {
                return false;
            }
            tmp[ch - 'a']--;
        }
        return true;
    }
}

class Solution {
    int[] mouths = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public int dayOfYear(String date) {
        int year = 0, mouth = 0, day = 0;
        for (int i = 0; i < 4; i++) {
            year = year * 10 + date.charAt(i) - '0';
        }
        for (int i = 5; i < 7; i++) {
            mouth = mouth * 10 + date.charAt(i) - '0';
        }
        for (int i = 8; i < 10; i++) {
            day = day * 10 + date.charAt(i) - '0';
        }

//        //判断闰年
//        if ((year % 100 != 0 && year % 4 == 0) || (year % 400 == 0)) {
//            mouths[2] = 29;
//        }



        int ret = 0;
        for(int i = 1; i<= mouth; i++) {
            ret += mouths[i];
        }
        ret += day;
        return ret;
    }
}


public class Test {
    public static void main(String[] args) {
        for (int year = 2000; year <= 2100; year++) {
            if ((year % 100 != 0 && year % 4 == 0) || (year % 400 == 0)) {
                printf("%d " , year);
            }
        }
    }
}
